/**
 * @file     str_match.hpp
 * @author   WMQ
 * @date     2024/12/12
 * @brief    KMP算法
 */

#ifndef STR_MATCH_HPP
#define STR_MATCH_HPP

#include <cstring>

/**
 * @brief KMP匹配算法
 */
template <int MAX_BUFF_DATA_LENGTH>
class StrMatch
{
public:
    /**
     * @brief 构造函数
     * @param[in] buff 要匹配数据的首地址
     * @param[in] buff_length 匹配的数据长度，不能大于MAX_BUFF_DATA_LENGTH
     */
    StrMatch(const char* buff, int buff_length)
    {
        if (buff == nullptr || buff_length > MAX_BUFF_DATA_LENGTH)
        {
            init_flag_ = false;
            return;
        }

        memcpy(buff_data_, buff, buff_length);
        buff_data_len_ = buff_length;

        PrefixFun(buff, buff_length);

        init_flag_ = true;
    }

    /**
     * @brief 从指定内存域中匹配数据
     * @param[in] buff 内存起始地址
     * @param[in] buff_length 内存长度
     * @param[out] current_index 当前匹配的位置
     * @param[out] match_len 已匹配的长度
     * @return
     *  false   操作失败 \n
     *  true    操作成功 \n
     */
    bool Match(const char* buff, int buff_length, int &current_index, int &match_len)
    {
        if (!init_flag_ || buff == nullptr)
        {
            return false;
        }

        int j = 0;
        int i = 0;
        for (; i < buff_length && j < buff_data_len_; i++)
        {
            while (j > 0 && buff[i] != buff_data_[j])
            {
                j = next_[j - 1];
            }

            if (buff[i] == buff_data_[j])
            {
                j++;
            }
        }

        match_len = j;
        current_index = i;
        return true;
    }

private:
    bool init_flag_ = false;                  /**< 是否初始化成功 */
    int next_[MAX_BUFF_DATA_LENGTH] {};       /**< next数组 */
    char buff_data_[MAX_BUFF_DATA_LENGTH] {}; /**< 要匹配的数据 */
    int buff_data_len_ = 0;                   /**< 要匹配数据的长度 */

    /**
     * @brief 计算每个字节值的前缀函数值
     * @param[in] buff 要匹配数据的起始地址
     * @param[in] buff_length 要匹配数据的长度
     */
    void PrefixFun(const char* buff, int buff_length)
    {
        next_[0] = 0;
        for (int i = 1; i < buff_length; i++)
        {
            int j = next_[i - 1];
            while (j > 0 && buff[i] != buff[j])
            {
                j = next_[j - 1];
            }

            if (buff[i] == buff[j])
            {
                j++;
            }
            next_[i] = j;
        }
    }
};

#endif